


#  707.设计链表



class LinkNode(object):
    def __init__(self,val=0,next=None):
        self.val = val
        self.next = next


class MyLinkedList(object):

    def __init__(self):
        self.head = LinkNode()
        self.length = 0


    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index<0 or index>=self.length:
            return -1
        count = 0
        p = self.head.next
        while p!=None:
            if count == index:
                return p.val
            p = p.next
            count = count + 1


    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        p = self.head
        newNode = LinkNode(val)
        newNode.next = p.next
        self.head.next = newNode
        self.length = self.length + 1
        return


    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        pre = self.head
        p = pre.next
        while p!=None:
            pre = p
            p = p.next
        newNode = LinkNode(val)
        pre.next = newNode
        self.length = self.length + 1
        return


    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        if index==self.length:
            self.addAtTail(val)
            return
        elif index>self.length:
            return
        if index==0:
            newNode = LinkNode(val)
            newNode.next = self.head.next
            self.head.next = newNode
            self.length = self.length + 1
            return
        else:
            p = self.head.next
            count = 0
            while count<index-1 and p.next!=None:
                count = count + 1
                p = p.next
            newNode = LinkNode(val)
            newNode.next = p.next
            p.next = newNode
            self.length = self.length + 1
            return



    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        if index<0 or index>self.length:
            return
        elif index == 0:
            p = self.head.next
            self.head.next = p.next
            self.length = self.length - 1
            return
        elif index==self.length:
            p = self.head.next
            count = 0
            while count < self.length - 1:
                p = p.next
                count = count + 1
            p.next = None
        else:
            p = self.head.next
            quick = p.next
            count = 0
            while count < index - 1 and quick.next != None:
                p = p.next
                quick = quick.next
                count = count + 1
            p.next = quick.next
            self.length = self.length - 1
            return

    def printList(self):
        p = self.head
        while p!=None:
            print(p.val,end='\t')
            p = p.next
        print()

if __name__ == "__main__":

    obj = MyLinkedList()

    obj.addAtIndex(0,10)
    obj.printList()
    obj.addAtIndex(0, 20)
    obj.printList()
    obj.addAtIndex(1, 30)
    obj.printList()
    # obj.addAtHead(6)
    # # obj.printList()
    # obj.addAtTail(4)
    # obj.printList()
    # print(obj.get(4))
    # obj.addAtHead(4)
    # obj.printList()
    # obj.addAtIndex(5,0)
    # obj.printList()
    # obj.addAtHead(6)
    # obj.printList()
    # obj.addAtTail(3)
    # obj.printList()
    # obj.addAtIndex(1,2)
    # obj.printList()
    # obj.get(1)
    #
    # obj.deleteAtIndex(1)
    # obj.printList()
    # obj.get(1)
    # ["MyLinkedList", "addAtHead", "addAtHead", "addAtHead", "addAtIndex", "deleteAtIndex", "addAtHead", "addAtTail","get", "addAtHead", "addAtIndex", "addAtHead"]
    # [[], [7], [2], [1], [3, 0], [2], [6], [4], [4], [4], [5, 0], [6]]